package ch04.shortest_path;

/*
    第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
    第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
    第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：如果d（v） > d (u) + w(u,v)，则返回false，表示途中存在从源点可达的权为负的回路。
*/
public class BellManFord {
    static class Edge {
        public int a;
        public int b;
        public int weight;

        public Edge(int a, int b, int weight) {
            this.a = a;
            this.b = b;
            this.weight = weight;
        }
    }

    static Edge[] edges;
    static int n = 6;
    static int edNum = 8;

    static double[] dis;
    static final double INF = Double.MAX_VALUE;

    static void init() {
        dis = new double[n + 1];
        edges = new Edge[edNum + 1];
        for (int i = 1; i <= n; i++) {
            dis[i] = INF;
        }
        dis[1] = 0;
        edges[1] = new Edge(4, 2, -2);
        edges[2] = new Edge(3, 5, 4);
        edges[3] = new Edge(5, 6, 1);
        edges[4] = new Edge(1, 5, 5);
        edges[5] = new Edge(2, 5, 7);
        edges[6] = new Edge(1, 3, 3);
        edges[7] = new Edge(3, 4, 5);
        edges[8] = new Edge(1, 2, 5);

    }

    static boolean bellFord() {
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= edNum; j++) {
                if (dis[edges[j].b] > dis[edges[j].a] + edges[j].weight) {
                    dis[edges[j].b] = dis[edges[j].a] + edges[j].weight;
                }
            }
        }
        boolean flag = false;
        for (int j = 1; j <= edNum; j++) {
            if (dis[edges[j].b] > dis[edges[j].a] + edges[j].weight) {
                flag = true;
                break;
            }
        }
        return flag;
    }

    static void print() {
        for (int i = 1; i <= n; i++) {
            System.out.println(dis[i]);
        }
    }

    public static void main(String[] args) {
        init();
        boolean b = bellFord();
        System.out.println(b);
        print();
    }
}
